/**
 * \* Created with IntelliJ IDEA.
 * \* User: 冯若航
 * \* Date: 2021/6/16
 * \* Time: 22:25
 * \* To change this template use File | Settings | File Templates.
 * \* Description:
 * \
 */
public class 解数独 {
    public void solveSudoku(char[][] board) {
        backtrack(board,0,0);
    }
    boolean backtrack(char[][] board,int i,int j){
        int m=9,n=9;
        //到达最后一列转入下一行
        if(j==n){
            return backtrack(board,i+1,0);
        }
        //找到正确答案
        if(i==m){
            return true;
        }
        //如果已经预设了数字则跳过
        if(board[i][j]!='.'){
            return backtrack(board,i,j+1);
        }
        for(char ch='1';ch<='9';ch++){
            //跳过不合法的选择
            if(!isValid(board,i,j,ch)){
                continue;
            }
            //做出选择
            board[i][j]=ch;
            //如果找到可行解，立即结束
            if(backtrack(board,i,j+1)){
                return true;
            }
            //撤销选中
            board[i][j]='.';
        }
        //找不到合法解
        return false;
    }

    //判断在board[r][c]是否可以填入字符n
    boolean isValid(char[][] board,int r,int c,int n){
        for(int i=0;i<9;i++){
            //判断行是否存在重复的
            if(board[r][i]==n){
                return false;
            }
            //判断列
            if(board[i][c]==n){
                return false;
            }
            //判断九宫格
            if(board[(r/3)*3 + i/3][(c/3)*3 + i%3] == n){
                return false;
            }
        }
        return true;
    }
}